It is known that the efficiency with which data can be compressed and decompressed depends primarily on the buffer size and encoding implementation used. Executing a compression/decompression algorithm using software is slow and therefore not suited for high speed or real time applications. Executing the algorithm using hardware requires an amount of hardware that varies according to the degree of parallelism of the implementation technique employed. If too much hardware is required, it may be difficult to integrate the data compression algorithm into a controller.
A paper by Lempel and Ziv entitled "A Universal Algorithm for Sequential Data Compression", published in IEEE Transactions on Information Theory, May 1977, at pp. 337-343, describes an algorithm for efficiently compressing data.
This Lempel-Ziv l (LZl) algorithm is a sequential algorithm that compresses strings of binary data of variable length into a fixed length compressed binary format. It is implemented using a history buffer that contains the most recent bytes or words of a file in the correct sequence. Methodically, by repeated executions of a basic routine, new bytes are read as long as the sequence of incoming bytes is matched by a sequence in the history buffer, thereby generating a sequential stream of data. Since each incoming byte is sequentially compared with each byte in the history buffer, a significant amount of computation time is required, making this technique unsuitable for real time applications.
Commonly assigned U.S. Ser. No. 07/807,007, filed Dec. 31, 1991, (Docket AT991-030) describes a typical implementation of the LZl algorithm and then cites a number of patents (not deemed material to the present invention) which cover techniques toward improving the speed with which the LZl algorithm is executed or the amount of compression achieved.
This cited commonly assigned application describes a fully parallel architecture that implements the LZl algorithm in hardware. With a content addressable memory (CAM) serving as a history buffer, each incoming byte is compared simultaneously with all the bytes in the history buffer. This fully parallel hardware approach desirably provides the fastest execution of the LZl algorithm. However, it requires a separate comparator for each distinct buffer position (i.e., CAN address) and can only achieve the maximal efficiency (speed/hardware performance) when the history buffer is full; namely, after an initial loading period for each sector or input data field of the data storage medium. Therefore, if the sector is approximately the same size as the history buffer, the fully parallel implementation will require many redundant operations.
Since the size of a device controller chip is essentially the same as that of the chip needed to implement the purely parallel compression, a parallel compression chip cannot efficiently be used to perform compression in a device controller. The principal use for this fully parallel approach is for host data compression, where the compression chip is located in the host controller.
There is a need for a data compression/decompression apparatus and method which implements the LZl algorithm by use of a modular architecture that:
1. Divides the history buffer into a plurality of blocks, compares all bytes in a block in parallel, and scans the blocks sequentially;
2. Enables a designer to select any speed ranging from the slow sequential execution of the LZl algorithm to the above-described optimal parallel implementation by selecting a desired degree of parallelism in order to limit hardware costs to the needs of a particular application;
3. Is especially suitable for applications in which the data compression is performed in a device controller, where the required execution speed is approximately an order of magnitude less than that required to perform compression in a host controller; and
4. Is especially advantageous when an input data sector and history buffer contain approximately the same number of bytes.